'''
Created on Apr 12, 2012

@author: dolphinigle
'''

def ToBits(number, amt):
  assert 0 <= number < 2**amt
  bits = []
  for _ in range(amt):
    bits.append(number % 2)
    number /= 2
  bits.reverse()
  return bits

def FromBitToInt(bits):
  no = 0
  for k in bits:
    assert 0 <= k <= 1
    no *= 2
    no += k
  return no

# Rotates by 1 place to the left
def BitLeftRotate(bits, number):
  assert 0 <= number < 2**bits
  in_bits = ToBits(number, bits)
  for i in range(bits - 1):
    tmp = in_bits[i]
    in_bits[i] = in_bits[i+1]
    in_bits[i+1] = tmp
  return FromBitToInt(in_bits)

# Multiple left rotate
def MultiLeftRotate(bits, numbers, amt):
  assert amt >= 0
  if amt >= bits:
    return MultiLeftRotate(bits, numbers, amt % bits)
  
  ret = numbers
  for _ in range(amt):
    ret = BitLeftRotate(bits, ret)
  
  return ret

# To hex
def ToHex(bits, number):
  assert bits % 4 == 0;
  assert 0 <= number < 2**bits
  ret = []
  for _ in range(bits / 4):
    val = number % 16
    number /= 16
    if val < 10:
      ret.append(chr(ord('0') + val))
    else:
      ret.append(chr(ord('a') + (val-10)))
  ret.reverse()
  result = ''
  for c in ret:
    result += c
  return result

# To int
def HexToInt(hx):
  val = 0
  for i in hx:
    val *= 16
    if i >= '0' and i <= '9':
      val += ord(i) - ord('0')
    else:
      val += ord(i) - ord('a') + 10
  return val

def ModExp(number, exponent, modulo):
  assert exponent >= 0
  mult = number % modulo
  ret = 1
  while exponent:
    if exponent % 2:
      ret *= mult
      ret %= modulo
    exponent /= 2
    mult = (mult*mult) % modulo
  return ret

def ExtendedEuclid(a, b):
  original_a = a
  original_b = b
  a = abs(a)
  b = abs(b)
  
  swapped = 0
  if a < b:
    (a, b) = (b, a)
    swapped = 1;
  
  if not b:
    if swapped:
      return (0, 1)
    return (1, 0)
  
  s0 = 1
  s1 = 0
  t0 = 0
  t1 = 1
  
  r0 = a
  r1 = b
  
  while True:
    q = r0 / r1;
    r2 = r0 % r1;
    if r2 == 0:
      # stop, return the last value
      if original_a < 0:
        if swapped:
          t1 *= -1
        else:
          s1 *= -1
      if original_b < 0:
        if swapped:
          s1 *= -1
        else:
          t1 *= -1
      if swapped:
        return (t1, s1)
      else:
        return (s1, t1)
    # advance
    s2 = s0 - q * s1
    t2 = t0 - q * t1
    s0 = s1
    s1 = s2
    t0 = t1
    t1 = t2
    r0 = r1
    r1 = r2

def ModInverse(a, p):
  (i, _) = ExtendedEuclid(a, p)
  i %= p
  if i < 0:
    i += p
  return i
